package exam.dfs;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * dfs实现排列组合
 *
 * @author shenenlu 2021年05月05日 下午21:50:00
 */
public class ArrangementAndCombinationDfs {


    private int[]  numberList;

    private boolean[]  visited;

    private Stack<Integer> temp;

    private List<List<Integer>> result;


    public ArrangementAndCombinationDfs(int[] numberList){
        this.numberList = numberList;
        this.result = new ArrayList<>();
        this.temp = new Stack<>();
        this.visited = new boolean[numberList.length];
    }


    /**
     * C(n,k)组合dfs
     * 要求给出对于序列1~n 的取出k个元素的各种取法
     * 。采用DFS模拟组合时，可看做节点i与节点j(j = i+1, … , n)都相连接，然后DFS遍历整张有向图
     */
    public void combinationDfs(int index, int k){
        if( temp.size() == k ){
            result.add(new ArrayList<>(temp));
            return;
        }
        if(  k > numberList.length || k < 0 ){
            return;
        }
        if( index == numberList.length ){
            return;
        }
        for (int i = index; i < numberList.length; i++) {
            temp.push(numberList[i]);
            combinationDfs(i + 1, k);
            temp.pop();
        }
    }

    /**
     * A(n,k)排列dfs
     * DFS实现排列与组合相类似，唯一不同之处在于，节点i与其他所有节点都连接。因此，所构造的图是一个完全连通图
     */
    public void arrangementDfs(int k){
        if( temp.size() == k ){
            result.add(new ArrayList<>(temp));
            return;
        }
        if( k > numberList.length || k < 0 ){
            return;
        }
        for (int i = 0; i < numberList.length; i++) {
            // nums[i] has not been visited
            if ( !visited[i] ) {
                temp.push(numberList[i]);
                visited[i] = true;
                arrangementDfs(k);
                visited[i] = false;
                temp.pop();
            }
        }
    }




    public static void main(String[] args) {
        int[] numberList = new int[]{1,2,3,4};
        ArrangementAndCombinationDfs arrangementAndCombinationDfs = new ArrangementAndCombinationDfs(numberList);
//        arrangementAndCombinationDfs.combinationDfs(0, 2);
        arrangementAndCombinationDfs.arrangementDfs(3);
        arrangementAndCombinationDfs.result.forEach(System.out::println);


    }

}
